package com.swf.seed.algorithms.problem;

/**
 * ClassName: Eratosthenes <br/>
 * Function: 筛选求质数. <br/>
 * Reason: 首先假设要检查的数是N好了，则事实上只要检查至N的开根号就可以了，道理很简单，假设<br/>
 * A*B=N，如果A大于N的开根号，则事实上在小于A之前的检查就可以先检查到B这个数可以整<br/>
 * 除N。不过在程式中使用开根号会精确度的问题，所以可以使用i*i<=N进行检查，且执行更快 。<br/>
 * 再来假设有一个筛子存放1～N，例如：<br/>
 * 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21........N<br/>
 * 先将2的倍数筛去：<br/>
 * 2 3 5 7 9 11 13 15 17 19 21........N<br/>
 * 再将3的倍数筛去：<br/>
 * 2 3 5 7 11 13 17 19 ........N<br/>
 * 再来将5的倍数筛去，再来将7的质数筛去，再来将11的倍数筛去........，如此进行到最后留下的<br/>
 * 数就都是质数，这就是Eratosthenes筛选方法（EratosthenesSieveMethod）。 <br/>
 * date: 2015-1-20 下午3:23:56 <br/>
 *
 * @author shenwf10476
 * @version
 * @since JDK 1.6
 */
public class Eratosthenes {
	public int prime(int n){
		int[] prime = new int[n+1];
		for (int i=2;i<=n;i++){
			prime[i] = 1;
		}
		for (int i=2;i*i<=n;i++){
			if (prime[i]==1){
				for (int j=2*i;j<=n;j++){
					if (j%i==0){
						prime[j] = 0;
					}
				}
			}
		}
		int count = 0;
		for (int i=2;i<=n;i++){
			if (prime[i]==1){
				System.out.printf("%5d",i);
				count ++;
				if (count%10==0){
					System.out.println();
				}
			}
		}
		return 0;
	}

	public static void main(String[] args) {
		new Eratosthenes().prime(2000);
	}
}
